//
// Created by dengspc on 2019/2/13.
//

#ifndef INC_010_ALGORITHM_AdjDiGraph_H
#define INC_010_ALGORITHM_AdjDiGraph_H

#include <iostream>
#include <cassert>
#include <queue>
#include <stack>
#include "DiGraph.h"
#include "Bag.h"

#define BLACK false
#define WHITE true

using namespace std;
typedef bool Color;

class AdjDiGraph:public DiGraph{
private:
    int v;//顶点（vertex）数量
    int e;//边数量（edge)
    Bag<int>* adjs;//背包数组，下标对应顶点序号，包里面的数据是与此顶点直接连接的顶点集合
public:
    AdjDiGraph(int v = 0){
        this->v=v;
        this->e = 0;
        adjs = new Bag<int>[v];
        for (int i =0; i < v; ++i) {
            adjs[i] = *(new Bag<int>());
        }
    }

    ~AdjDiGraph(){
        delete[] adjs;
    }

    int V() {
        return v;
    }//求顶点数量
    int E() {
        return e;
    }//求边数量
    void addEdge(int v, int w) {
        assert(v<this->v);
        assert(w<this->v);
        adjs[v].add(w);
        e++;
    }//向图中添加一条边 v w
    vector<int>* adj(int v) {
        return adjs[v].getVector();
    }//与v相邻的顶点集合
    void print() {
        cout<<this->v<< " vertices, " << this->e << " edges" << endl;
        cout<<"numOfSelfLoops: " << numOfSelfLoops()<<endl;
        for (int i =0; i < this->v; ++i) {
            cout<< i << ": ";
            vector<int>* vector1 = adj(i);
            int size = vector1->size();
            for (int j =0; j < size; ++j) {
                cout << (*vector1)[j] << " ";
            }
            cout<< " degree = "<< degree(i) <<endl;
            delete vector1;
        }
        cout<< "maxDegree = "<< maxDegree() <<endl;
        cout<< "avgDegree = "<< avgDegree() <<endl;

    }//打印
    int numOfSelfLoops() {
        int count =0;
        for (int i =0; i < V(); i++) {
            vector<int>* vector1 = adj(i);
            int size = vector1->size();
            for (int j =0; j < size; ++j) {
                if((*vector1)[j] == i)
                    count++;
            }
            delete vector1;
        }
        return count;
    }//计算自环的个数

    DiGraph* reverse(){
        DiGraph* diGraph = new AdjDiGraph(V());
        for (int i = 0; i < v; ++i) {
            vector<int>* vector1 = adjs[i].getVector();
            int size = vector1->size();
            for (int j = 0; j < size; ++j) {
                int w = (*vector1)[j];
                diGraph->addEdge(w,i);
            }
            delete vector1;
        }
        return diGraph;
    }
};


/**
 * 给定一个或者一组顶点，判读出能到达那些顶点
 */
class DirectedDFSImpl:public DirectedDFS{
private:
    bool* marks;///标记对应点是否被访问过 true = 访问过

    void dfs(AdjDiGraph* g, int source){
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            if(!marks[(*vector1)[i]]){
                marks[(*vector1)[i]] = true;
                dfs(g,(*vector1)[i]);
            }
        }
        delete vector1;
    }
public:
    DirectedDFSImpl(AdjDiGraph*  g, int source){
        marks = new bool[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        dfs(g,source);
    }

    DirectedDFSImpl(AdjDiGraph*  g, vector<int>* sources){
        marks = new bool[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        int souceSize = sources->size();
        for (int j = 0; j < souceSize; ++j) {
            int source = (*sources)[j];
            if(!marks[source])
                dfs(g,source);
        }
    }

    ~DirectedDFSImpl(){
        delete[] marks;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通
};



/**
 * 参考命题A续
 * 深度优先搜索，不能得到最短路径
 * 图路径算法
 */
class DepthFirstDirectedPaths:public DirectedPaths{
private:
    void dfs(AdjDiGraph* g, int source){
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            int pos = (*vector1)[i];
            if(!marks[pos]){
                marks[pos] = true;
                edges[pos] = source;
                dfs(g,pos);
            }
        }

        delete vector1;
    }
public:
    DepthFirstDirectedPaths(AdjDiGraph*  g, int source){
        marks = new bool[g->V()];
        edges = new int[g->V()];
        this->source = source;
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        dfs(g,source);
    }

    ~DepthFirstDirectedPaths(){
        delete[] marks;
        delete[] edges;
    }
};

/**
 * 广度优先搜索
 */
class BreadthFirstDirectedPaths:public DirectedPaths{
private:
    queue<int>* queue1;
    void bfs(AdjDiGraph* g, int s){
        queue1->push(s);
        while(!queue1->empty()) {
            int source = queue1->front();
            queue1->pop();
            vector<int> *vector1 = g->adj(source);
            int size = vector1->size();
            for (int i = 0; i < size; ++i) {
                int pos = (*vector1)[i];
                if (!marks[pos]) {
                    queue1->push(pos);
                    marks[pos] = true;
                    edges[pos] = source;
                }
            }
            delete vector1;
        }

    }
public:
    BreadthFirstDirectedPaths(AdjDiGraph*  g, int source){
        marks = new bool[g->V()];
        edges = new int[g->V()];
        this->source = source;
        this->queue1 = new queue<int>();
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        bfs(g,source);
    }

    ~BreadthFirstDirectedPaths(){
        delete[] marks;
        delete[] edges;
        delete queue1;
    }
};

/**
 * 图存在环？（除去平行边和自环）
 */
class DfsDirectedCycle:public DirectedCycle{
private:
    bool* marks;///标记对应点是否被访问过 true = 访问过
    int* edges;//边集合，类似18-uf工程中的并查集，不断递归，最终指向source edges[?] = source。总体来说存储路径
    bool* onStack; // 当前节点是否在访问栈中
    stack<int>* cycles = NULL;//环的路径栈

    /**
     * 能被dfs访问的，肯定在同一个连通分量里面
     * @param g
     * @param source
     * @param preSource
     */
    void dfs(AdjDiGraph* g, int source){
        marks[source] = true;
        onStack[source] = true;//标记当前顶点在访问栈中
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            if(hasCycle()){
                return ;
            }
            int w = (*vector1)[i];
            if(!marks[w]){
                edges[w] = source;
                dfs(g,w);
            }else if(onStack[w]) {//当前节点（w）被访问过 且 w正在访问顶顶栈里面,那么则存在环
                cycles = new stack<int>();
                for(int x = source; x!=w;x=edges[x])//循环从source开始，到转追述到w,（source->w） 加入w,source即为一环
                    cycles->push(x);
                cycles->push(w);
                cycles->push(source);
            }
        }

        onStack[source] = false;//测回标记当前顶点在访问栈中
        delete vector1;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通

public:
    DfsDirectedCycle(AdjDiGraph*  g){
        marks = new bool[g->V()];
        edges = new int[g->V()];
        onStack = new bool[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
            onStack[i] = false;
        }
        for (int i = 0 ; i < g->V(); ++i) {
            if(!marked(i))
                dfs(g,i);
        }
    }

    ~DfsDirectedCycle(){
        delete[] marks;
        delete[] edges;
        delete[] onStack;
        if(cycles!=NULL){
            delete cycles;
        }
    }

    bool hasCycle() {
        return cycles != NULL;
    }

    stack<int>* cycle(){
        return cycles;
    }//环的路径
};

/**
 * 顺序定义
 */
class DirectedOrderImpl:public DirectedOrder{
private:
    bool* marks;///标记对应点是否被访问过 true = 访问过
    queue<int>* preOder = new queue<int>();//前序数组
    queue<int>* postOder = new queue<int>();//后序序数组
    stack<int>* reversePostOrder = new stack<int>();//后序逆数组，也是拓扑排序的结果

    void dfs(DiGraph* g, int source){
        preOder->push(source);
        marks[source] = true;
        vector<int>* vector1 = g->adj(source);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            int w = (*vector1)[i];
            if(!marks[w]){

                dfs(g,w);

            }
        }
        postOder->push(source);
        reversePostOrder->push(source);

        delete vector1;
    }
public:
    DirectedOrderImpl(DiGraph*  g){
        marks = new bool[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        for (int i = 0 ; i < g->V(); ++i) {
            if(!marks[i])
                dfs(g,i);
        }
    }
    ~DirectedOrderImpl(){
        delete preOder;
        delete postOder;
        delete reversePostOrder;
    }
    queue<int>* pre() {
        return preOder;
    }//递归的前序
    queue<int>* post() {
        return postOder;
    }//递归的后序
    stack<int>* reversePost() {
        return reversePostOrder;
    }//递归的逆后序
};


/**
 * 拓扑排序API
 * 当且仅当一副有向图无环才可拓扑排序
 * 定义：给定一幅有向图，将所有的顶点排序，使得所有的边都从排在前面的元素指向排在后面的元素
 */
class TopologicalImpl:public Topological{
private:
    queue<int>* orders = NULL;
public:
    TopologicalImpl(AdjDiGraph*  g){
        DirectedCycle* cycle = new DfsDirectedCycle(g);
        if(!cycle->hasCycle()){
            DirectedOrder* order1 = new DirectedOrderImpl(g);
            stack<int>* stack1 = order1->reversePost();
            orders = new queue<int>();
            while(!stack1->empty()){
                orders->push(stack1->top());
                stack1->pop();
            }
            delete order1;
        }
        delete cycle;
    }
    ~TopologicalImpl(){
       delete orders;
    }
    bool isDAG() {
        return orders!=NULL;
    }// 是有向无环图吗
    queue<int>* order() {
        return orders;
    }// 拓扑有序的所有顶点
};


/**
 * 连通分量
 */
class DepthFirstKosarajuSCC:public KosarajuSCC{
private:
    bool* marks;//标记对应点是否被访问过 true = 访问过
    int* ids;//下标对应顶点序号，值对应为所在连通分量的序号
    int counts = 0;//图g的连通分量的数量

    void dfs(AdjDiGraph* g, int v){
        marks[v] = true;
        ids[v] = counts;
        vector<int>* vector1 = g->adj(v);
        int size = vector1->size();
        for (int i = 0 ; i < size; ++i) {
            if(!marks[(*vector1)[i]]){
                dfs(g,(*vector1)[i]);
            }
        }

        delete vector1;
    }

    bool marked(int v) {
        return marks[v];
    }//v 与 source 是否连通

public:
    DepthFirstKosarajuSCC(AdjDiGraph*  g){
        marks = new bool[g->V()];
        ids = new int[g->V()];
        for (int i = 0 ; i < g->V(); ++i) {
            marks[i] = false;
        }
        //遍历所有顶点
        DiGraph* rg = g->reverse();
        DirectedOrder* dorder = new DirectedOrderImpl(rg);
        stack<int>* stack1 = dorder->reversePost();
        while(!stack1->empty()){
            int top = stack1->top();
            stack1->pop();
            if(!marks[top]){
                dfs(g,top);//遍历i所在连通分量的顶点，并标记在ids数组中
                counts++;//连通分量数量增加
            }
        }

        delete dorder;
    }

    ~DepthFirstKosarajuSCC(){
        delete[] marks;
        delete[] ids;
    }

    bool strongConnected(int v, int w){
        return ids[v] = ids[w];
    }//v 与 w 是否连通
    int count(){
        return counts;
    }// 连通分量的数量
    int id(int v){
        return ids[v];
    }// v所在连通分量的顶点(标识符)

};

#endif //INC_010_ALGORITHM_AdjDiGraph_H
